#include "vector_dinamico.h"
#include "heap.h"
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#include <time.h>

/* ******************************************************************
 *                DEFINICION DE LOS TIPOS DE DATOS					*
 * *****************************************************************/
 
struct _vector_dinamico {
	void** datos;
	size_t cant;
	size_t tam;
	vector_destruir_dato_t destructor;
};

/* ******************************************************************
 *                		FUNCIONES AUXILIARES						*
 * *****************************************************************/

// Intercambia los punteros.
// Pre: ambos son válidos.
// Post: los punteros fueron intercambiados.
static void swap_elem (void **a, void **b) {
	void *aux = *a;
	*a = *b;
	*b = aux;
}

/* ******************************************************************
 *                IMPLEMENTACION DE PRIMITIVAS						*
 * *****************************************************************/

// Crea un vector de tamaño tam. 'dtr' es una función capaz de destruir
// los elementos del vector. Si se recibe NULL, lógicamente,
// ésta no es aplicada.
// Post: vector es una vector vacío de tamaño tam.
vector_dinamico_t* vector_crear (size_t tam, vector_destruir_dato_t dtr) {
	vector_dinamico_t* vector = malloc (sizeof(vector_dinamico_t));
	if (!vector) return NULL;

	vector->datos = calloc (tam,sizeof(void*));
	if (!(vector->datos)) {
		free(vector);
		return NULL;
    }
	vector->tam = tam;
	vector->cant = 0;
	vector->destructor = dtr;
	return vector;
}

// Destruye el vector.
// Pre: el vector fue creado.
// Post: se eliminaron el vector y todos sus elementos.
void vector_destruir (vector_dinamico_t* vector) {
	if (!vector) return;
	if (vector->destructor) {
		for (size_t i = 0; i < (vector->tam); i++) {
			if ((vector->datos)[i]) vector->destructor ((vector->datos)[i]);
		}
	}
	free (vector->datos);
	free (vector);
}

// Cambia el tamaño del vector. 'nuevo_tam' debe ser igual o mayor que
// la posición del último elemento existente en el vector.
// Pre: el vector fue creado.
// Post: el vector cambió de tamaño a 'nuevo_tam' y devuelve true
// o el vector queda intacto y devuelve false si no se pudo cambiar el tamaño
// a 'nuevo_tam'.
bool vector_redimensionar(vector_dinamico_t* vector, size_t tam_nuevo) {
	if (!vector) return false;
	int i = (vector->tam)-1;
	while (i >= 0) {
		if ((vector->datos)[i]) break;
		i--;
	}
	if (tam_nuevo < i+1) return false;

	void** datos_nuevo = realloc(vector->datos, tam_nuevo * sizeof(void*));
	if (!datos_nuevo) return false;
	
	for (size_t i = (vector->tam); i < tam_nuevo; i++) datos_nuevo[i] = NULL;
	vector->datos = datos_nuevo;
	vector->tam = tam_nuevo;
	return true;
}

// Devuelve el dato guardado en la posición 'pos' del vector.
// Devuelve NULL si la posición es inválida.
// Pre: el vector fue creado.
// Post: el dato fue devuelto.
void* vector_obtener (vector_dinamico_t* vector, size_t pos) {
	if (!vector) return NULL;
	if (pos >= (vector->tam)) return NULL;
	void* valor = vector->datos[pos];
	return valor;
}

// Almacena el valor en la posición 'pos'. De estar ocupada, sobreescribe
// el dato almacenado.
// Pre: el vector fue creado y 'valor' debe ser válido.
// Post: se almacenó el valor en la posición pos. Devuelve false si la posición
// es inválida, y true si se guardó el valor con éxito.
bool vector_guardar (vector_dinamico_t* vector, size_t pos, void* valor) {
	if ((!vector) || (!valor)) return false;
	if (pos >= (vector->tam)) return false;
	
	if ((vector->datos)[pos]) { // la pos está ocupada
		if (vector->destructor) vector->destructor ((vector->datos)[pos]);
	} else { // la pos está vacía, sumo un elemento nuevo
		(vector->cant)++;
	}
	
	(vector->datos)[pos] = valor;
	return true;
}

// Saca el dato hallado en 'pos' y lo devuelve. El vector posee un elemento menos.
// Devuelve NULL si la posición es inválida o está vacía.
// Pre: el vector fue creado.
// Post: el dato fue sacado del vector y devuelto.
void* vector_borrar (vector_dinamico_t* vector, size_t pos) {
	if (!vector) return NULL;
	void* valor = vector_obtener (vector,pos);
	if (!valor) return NULL;
	(vector->datos)[pos] = NULL;
	(vector->cant)--;
	return valor;
}

// Devuelve el tamaño del vector.
// Pre: el vector fue creado.
size_t vector_tamanio (vector_dinamico_t* vector) {
	if (!vector) return 0;
    return (vector->tam);
}

// Devuelve la cantidad de elementos que posee el vector.
// Pre: el vector fue creado.
size_t vector_cantidad (vector_dinamico_t* vector) {
	if (!vector) return 0;
	return (vector->cant);
}

// Mezcla aleatoriamente los elementos del vector contemplando únicamente
// el rango entre 0 y la cantidad existente.
// Pre: el vector fue creado.
// Post: el vector fue mezclado aleatoriamente.
bool vector_mezclar (vector_dinamico_t* vector) {
	if (!vector) return false;
	
	size_t tope = vector_cantidad (vector);
	for (size_t i = 0; i < tope; i++) {
		int j = rand ();
		size_t pos = j % tope;
		swap_elem ( &( (vector->datos)[i] ) , &( (vector->datos)[pos] ) );
	}
	return true;
}

// Ordena el vector de menor a mayor utilizando heap-sort.
// Pre: el vector fue creado correctamente y es IZQUIERDISTA.
// Post: el vector fue ordenado de menor a mayor.
void vector_ordenar (vector_dinamico_t* vector, cmp_func_t cmp) {
	if (!vector) return;
	heapsort ( vector->datos , vector->cant , cmp );
}
